A computer network is a geographically distributed collection of interconnected subnetworks for transporting data between network nodes, such as computers. A local area network (LAN) is an example of such a subnetwork. Since management of a large number of subnetworks can prove burdensome, the network may contain smaller groups of one or more subnetworks that may be managed as separate routing domains or autonomous systems (AS). The network topology is defined by an arrangement of client nodes that communicate with one another, typically through one or more intermediate network nodes, such as a router or switch. As used herein, a client node is an endstation node that is configured to originate or terminate network communications. In contrast, an intermediate network node is a node that facilitates routing data and messages among the client nodes. Communications between network nodes are typically effected by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
The data packets transferred among the network nodes may include fixed-sized data cells and/or variable-sized data frames. Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables the client nodes and intermediate nodes to efficiently route the packet through the computer network. Often, a packet's network headers include at least a data-link (layer 2 ) header and an internetwork (layer 3 ) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
The data-link header provides information for transmitting the packet over a particular physical link (i.e., a communication medium), such as a point-to-point link, Ethernet link, wireless link, optical link, etc. To that end, the data-link header may specify a pair of “source” and “destination” network interfaces that are connected by the physical link. A network interface contains the mechanical, electrical and signaling circuitry and logic used to couple a network node to one or more physical links; each physical link may be coupled to a corresponding port on the network interface. The network is interface is often associated with a hardware-specific address, known as a media access control (MAC) address. Accordingly, the source and destination network interfaces in the data-link header are typically represented as source and destination MAC addresses. The data-link header may also store flow control, frame synchronization and error checking information used to manage data transmissions over the physical link.
The internetwork header provides information defining the packet's logical path (or “virtual circuit”) through the computer network. Notably, the path may span multiple physical links. The internetwork header may be formatted according to the Internet Protocol (IP), which specifies IP addresses of both a source and destination node at the end points of the logical path. Thus, the packet may “hop” from node to node along its logical path until it reaches the client node assigned to the destination IP address stored in the packet's internetwork header. After each hop, the source and destination MAC addresses in the packet's data-link header may be updated, as necessary. However, the source and destination IP addresses typically remain unchanged as the packet is transferred from link to link in the network.
In operation, a client node sends a data packet to a network interface of the intermediate network node. The intermediate network node determines how to process the packet, e.g., based on which network interface the packet is received. For example, the intermediate network node may perform a path switching function that simply re-directs the packet from one network interface to another. In this case, the packet may be transmitted over a network interface that has been previously associated with the packet's destination MAC address.
Alternatively, the intermediate network node may perform a path determination, or forwarding decision, function that selects the most appropriate network interface to forward the packet. Specifically, the intermediate network node may parse a destination IP address from the packet's internetwork header and perform an “address lookup” operation to locate routing information corresponding to the parsed address. Here, routing information is broadly understood to include any information, such as adjacency information, bridge-forwarding information, etc., that may be used to determine the packet's next hop, and, in some cases, provide other services such as quality-of-service, billing, and so forth.
The intermediate network node often stores its routing information in a routing information base (RIB). The RIB is a searchable data structure in which network addresses are mapped to their associated routing information. For purposes of discussion, it will be assumed that a RIB is configured as a routing table, and thus the terms “routing table” and “RIB” will be used interchangeably hereinafter. However, those skilled in the art will understand that the RIB need not be organized as a table, and alternatively may be another type of searchable data structure. Although the intermediate network node's RIB may be configured with a predetermined set of routing information, the node also may dynamically acquire (“learn”) network routing information as it sends and receives data packets. When a packet is received at the intermediate network node, the packet's destination IP address may be used to identify a RIB entry containing routing information associated with the received packet. Among other things, the packet's routing information indicates the packet's next-hop address, so the packet's layer-2 (MAC) information can be appropriately modified and the packet transmitted to its next destination.
To ensure that its RIB contains up-to-date routing information, the intermediate network node may cooperate with other intermediate nodes to disseminate routing information representative of the current network topology. For example, suppose the intermediate network node detects that one of its neighboring nodes (i.e., adjacent network nodes) becomes unavailable, e.g., due to a link failure or the neighboring node going “off-line,” etc. In this situation, the intermediate network node can update the routing information stored in its RIB to ensure that data packets are not routed to the unavailable network node. Furthermore, the intermediate node also may communicate this change in network topology to the other intermediate network nodes so they, too, can update their local RIBs and bypass the unavailable node. In this manner, each of the intermediate network nodes becomes “aware” of the change in topology.
Typically, routing information is disseminated among the intermediate network nodes in accordance with a predetermined network communication protocol, such as a link-state protocol. Examples of conventional link-state protocols include, but are not limited to, the Open Shortest Path First (OSPF) protocol and the Intermediate-System-to-Intermediate-System (IS-IS) protocol. The OSPF protocol is described in more detail in Request for Comments (RFC) 2178, entitled OSPF Version 2, dated April 1998, which is incorporated herein by reference in its entirety. The IS-IS protocol is described in more detail in RFC 1195, entitled Use of OSI IS-IS for Routing in TCP/IP and Dual Environments, dated December 1990, which is incorporated herein by reference in its entirety.
Conventional link-state protocols use link-state packets (or “advertisements”) for exchanging routing information between interconnected intermediate network nodes. As used herein, a link-state packet (LSP) generally describes any message used by a routing protocol for communicating routing information among interconnected intermediate network nodes, i.e., routers and switches. Operationally, a first intermediate network node may generate a LSP and “flood” (i.e., transmit) the packet over each of its network interfaces coupled to other intermediate network nodes. Thereafter, a second intermediate network node may receive the flooded LSP and update its RIB based on routing information contained in the received LSP. Next, the second intermediate node may flood the received LSP over each of its network interfaces, except for the interface at which the LSP was received. This flooding process may be repeated until each interconnected intermediate node has received the LSP and updated its local RIB.
In practice, each intermediate network node typically generates and disseminates a LSP whose routing information includes a list of the intermediate node's neighboring network nodes and one or more “cost” values associated with each neighbor. As used herein, a cost value associated with a neighboring node is an arbitrary metric used to determine the relative ease/burden of communicating with that node. For instance, the cost value may be measured in terms of the number of hops required to reach the neighboring node, the average time for a packet to reach the neighboring node, the amount of network traffic or available bandwidth over a communication link coupled to the neighboring node, etc.
As noted, LSPs are usually flooded until each intermediate network node has received a LSP from each of the other interconnected intermediate nodes. Then, each of the intermediate nodes can construct the same “view” of the network topology by aggregating the received lists of neighboring nodes and cost values. To that end, each intermediate network node may input this received routing information to a “shortest path first” (SPF) calculation that determines the lowest-cost network paths that couple the intermediate node with each of the other network nodes. For example, the Dijkstra algorithm is a conventional technique for performing such a SPF calculation, as described in more detail in Section 12.2.4 of the text book Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein. Each intermediate network node updates the routing information stored in its local RIB based on the results of its SPF calculation. More specifically, the RIB is updated to correlate destination nodes with network interfaces or ports associated with the lowest-cost paths to reach those nodes, as determined by the SPF calculation.
Intermediate network nodes often execute a single “running context,” i.e., a process or thread, that is configured to perform the following ordered sequence of events: receive a LSP, perform a SPF calculation and RIB update based on the contents of the received LSP, then flood the received LSP. Because the SPF calculation and RIB update consume considerable amounts of processing time and resources in the intermediate network node, packet flooding is often delayed an unreasonable amount of time until these routing computations are completed.
As a result of these conventional flooding delays, routing information is not disseminated efficiently among the intermediate network nodes. For instance, due to delays in receiving updated network topology information, some of the intermediate nodes may continue to forward packets based on out-dated routing information. This, in turn, can lead to undesirable network effects such as “micro-loops,” which are discussed in more detail in U.S. patent application Ser No. 10/868,721 to Vasseur et al., entitled Avoiding Micro-Loops Upon Failure of Fast Reroute Protected Links, which is hereby incorporated by reference as though fully set forth herein.
In addition, the conventional flooding delays also may create a backlog of LSPs waiting to be flooded in the intermediate network node. That is, while the computationally-intensive SPF and RIB computations are being performed, LSPs received at the intermediate node may continue to deplete the node's available buffer memory and/or receive and transmission queues until one or more of these memory resources becomes full. Consequently, newly-received data packets, such as LSPs, may become lost or “dropped” at the intermediate node due to the lack of available memory resources.
One prior solution for reducing conventional flooding delays utilizes separate processes or threads that respectively perform flooding operations and routing-table computations, i.e., SPF and RIB computations. However, this is not always practically feasible and requires major re-writing of applications. The idea outlined in this document is an optimization of flooding and SPF/RIB update computation processing performed within a single running context.